/*
COPYRIGHT NOTICE: This software is provided by Canada Post Corporation (CPC). 
It can be used for postal ID-tag applications only. The software may be 
freely distributed and/or modified. A condition of such distribution is that 
this copyright notice is always included in the comments heading the software. 
This software is licensed "as is" without any other warranty of any kind. 
CPC expressly disclaims all warranties or conditions including, but not 
limited to, implied warranties or conditions of merchantability and fitness 
for particular purpose and those arising by statute or otherwise in law or 
from course of dealing or usage of trade. In no event shall CPC be liable 
for any direct, indirect, special, incidental, consequential or other damages 
arising out of this software even if CPC has been advised of the possibility 
of such damages in advance.
*/
/* $Id$ */
/* $Log$ */
/* REED-SOLOMON ENCODER FOR 0-1 CODES OVER GF(23).
Description: This program receives a 56 bit string of {0,1} representing data 
to be encoded and it generates a 78-bit string of {0,1} representing encoded 
data as the output.

The input consists of 14 four bit data symbols in the range 0-15. To this are 
added 4 five bit parity symbols which are determined by encoding this data with 
an (18,14) Reed-Solomon code over GF(23). The parity symbols are output 
according to a lookup table which restricts the run length of consecutive zeros. 
The data symbols are output as received. It is expected that the generation of 
the 56 data bits will be such that the run length of consecutive zeros will 
also be restricted to no more than 4.

Note that symbols 16-22 are never used in the data field of the Reed-Solomon 
code, as the 4 bit data are mapped onto the integers 0-15.

The final output is the 56 (14x4) data bits followed by the 20 (4x5) parity bits 
with a single start and stop bit (1) appended to each end of the sequence.
*/
static char rcsid[] = "$Id$";
#include <stdio.h>
#include <string.h>

/* global constants */

#include "common.h"
/* Define data type for small integers. */
#define INT8 unsigned char
#define SINT8 char
#define BOOLEAN char
const INT8 n = 18;     /* total number of symbols */
const INT8 k = 14;     /* number of 4 bit data symbols */
const INT8 k4 = 56;    /* 4 * k */
const INT8 n_k = 4;    /* n - k */
const INT8 k_1 = 13;   /* k - 1 */
const INT8 prime = 23;
const INT8 gen[5] = { 9, 17, 10,  2,  1 };
const INT8 lookup[23] = {
   31, 30, 29, 28, 27, 26, 25, 23, 22, 21, 20,
   19, 18, 17, 24, 15, 14, 13, 12, 11, 10,  9,  8
};
/* function prototypes */
void encode(int binary[], int codeword[]);
/* main program */
void main (int argc, char *argv[])
{
  int i, j;
  FILE *fd; 
  char *cp;
  char buf[80];   
  int codeword[18];
  int binary[56];
  int nline;
  if (argc < 2) {
    fprintf (stderr,"\n%s\n",rcsid);
    fprintf (stderr,"\nReed-Solomon encoder for 0-1 codes over GF(23).\n\n");
    fprintf (stderr,"Usage: encode23 filename\n\n");
    exit(1);
  }

cp = argv[1];

  if ((fd = fopen (cp, "r")) == NULL) {
     fprintf (stderr, "Unable to open input file %s.\n", cp);
     exit(1);
  }
  while (fgets(buf,sizeof(buf),fd)) {
     ++nline;
     j = strlen(buf);
     while ((j > 0) && (buf[j-1] == '\n' || buf[j-1] == '\r' || buf[j-1] == ' '))
       j = j - 1;
     
     if (j == 0) continue;
     if (j != k4) {
	fprintf(stderr,"\nSkipping line %d due to incorrect length %d.\n",nline,j);
	continue;
     }
     for (i = 0; i < k4; i++) {
	if (buf[i] != '0' && buf[i] != '1') {
	   fprintf (stderr, "ERROR - Invalid input at line %d.\n", nline);
	   fprintf (stderr, "        Invalid character at position %d.\n", i);
	   exit(1);
	} else {
	   binary[i] = buf[i] - '0';
	}
     }
     encode(binary,codeword);
/* Print out the full codeword, the k 4-bit data symbols first
   followed by the n-k parity symbols according to the lookup table.
*/
     printf("1"); /* start bit */
     for (i = 0; i < k; i++)  {
	printf ("%1o", (codeword[i] >> 3) & 1);
	printf ("%1o", (codeword[i] >> 2) & 1);
	printf ("%1o", (codeword[i] >> 1) & 1);
	printf ("%1o", codeword[i] & 1);
     }
     for (i = k; i < n; i++) {
	printf ("%1o", (lookup[codeword[i]] >> 4) & 1);
	printf ("%1o", (lookup[codeword[i]] >> 3) & 1);
	printf ("%1o", (lookup[codeword[i]] >> 2) & 1);
	printf ("%1o", (lookup[codeword[i]] >> 1) & 1);
	printf ("%1o", lookup[codeword[i]] & 1);
     }
     printf("1"); /* stop bit */
     printf ("\n");
  }
  exit(0);
}
void encode (int binary[], int codeword[])
{
   int mess[14], z, i, l;
/* Convert the message data from binary to GF(23) (4 bit) symbols. */
   for (i = 0; i < k; i++) {
      mess[i] =  (binary[4 * i + 0] & 1);
      mess[i] <<= 1;
      mess[i] ^= (binary[4 * i + 1] & 1);
      mess[i] <<= 1;
      mess[i] ^= (binary[4 * i + 2] & 1);
      mess[i] <<= 1;
      mess[i] ^= (binary[4 * i + 3] & 1);
   }

/* Initialize the parity symbols at the start of codeword. */
   for (i = 0; i < n_k; i++)
     codeword[i] = 0;
/* Reverse and complement the message and move to the end of codeword. */
   for (i = n_k; i < n; i++)
     codeword[i] = mess[n - i - 1] ^ 15;

/* Encode the message by dividing by the generator polynomial. */
   for (z = k_1; z >= 0; z--) {
      for (l = 0; l <= n_k; l++) {
	 codeword[z + l] = (codeword[z + l] - gen[l] * codeword[n_k + z]) % prime;
      }
   }

/* Make sure the parity symbols are in the range 0 to prime-1. */
/* Also reverse and move to the end of the array. */
   for (i = 0; i < n_k; i++) {
      if (codeword[i] < 0)
	codeword[i] *= -1;
      else if (codeword[i] > 0)
	codeword[i] = prime - codeword[i];
      codeword[n - i - 1] = codeword[i];
   }
/* Store the original data symbols at the start of the array. */
   for (i = 0; i < k; i++)
     codeword[i] = mess[i];

}}
